The present invention relates to the field of data compression and decompression systems; particularly, the present invention relates to a method and apparatus for lossless and lossy encoding and decoding of data in compression/decompression systems.
Data compression is an extremely useful tool for storing and transmitting large amounts of data. For example, the time required to transmit an image, such as a facsimile transmission of a document, is reduced drastically when compression is used to decrease the number of bits required to recreate the image.
Many different data compression techniques exist in the prior art. Compression techniques can be divided into two broad categories, lossy coding and lossless coding. Lossy coding involves coding that results in the loss of information, such that there is no guarantee of perfect reconstruction of the original data. The goal of lossy compression is that changes to the original data are done in such a way that they are not objectionable or detectable. In lossless compression, all the information is retained and the data is compressed in a manner which allows for perfect reconstruction.
In lossless compression, input symbols or intensity data are converted to output codewords. The input may include image, audio, one-dimensional (e.g., data changing spatially or temporally), two-dimensional (e.g., data changing in two spatial directions (or one spatial and one temporal dimension)), or multi-dimensional/multi-spectral data. If the compression is successful, the codewords are represented in fewer bits than the number of bits required for the uncoded input symbols (or intensity data). Lossless coding methods include dictionary methods of coding (e.g., Lempel-Ziv), run length encoding, enumerative coding and entropy coding. In lossless image compression, compression is based on predictions or contexts, plus coding. The JBIG standard for facsimile compression (ISO/IEC 11544) and DPCM (differential pulse code modulationxe2x80x94an option in the JPEG standard (ISO/IEC 10918)) for continuous-tone images are examples of lossless compression for images. In lossy compression, input symbols or intensity data are quantized prior to conversion to output codewords. Quantization is intended to preserve relevant characteristics of the data while eliminating unimportant characteristics. Prior to quantization, lossy compression system often use a transform to provide energy compaction. JPEG is an example of a lossy coding method for image data.
Recent developments in image signal processing continue to focus attention on a need for efficient and accurate forms of data compression coding. Various forms of transform or pyramidal signal processing have been proposed, including multi-resolution pyramidal processing and wavelet pyramidal processing. These forms are also referred to as subband processing and hierarchical processing. Wavelet pyramidal processing of image data is a specific type of multi-resolution pyramidal processing that may use quadrature mirror filters (QMFs) to produce subband decomposition of an original image. Note that other types of non-QMF wavelets exist. For more information on wavelet processing, see Antonini, M., et al., xe2x80x9cImage Coding Using Wavelet Transformxe2x80x9d, IEEE Transactions on Image Processing, Vol. 1, No. 2, April 1992; Shapiro, J., xe2x80x9cAn Embedded Hierarchical Image Coder Using Zerotrees of Wavelet Coefficientsxe2x80x9d, Proc. IEEE Data Compression Conference, pgs. 214-223, 1993. For information on reversible transforms, see Said, A. and Pearlman, W. xe2x80x9cReversible Image Compression via Multiresolution Representation and Predictive Codingxe2x80x9d, Dept. of Electrical, Computer and Systems Engineering, Renssealaer Polytechnic Institute, Troy, N.Y. 1993.
Quantization of wavelet coefficients results in pleasing images because wavelet filters are overlapped. In contrast, quantization of block-based, non-overlapped transform coefficients suffer from artifacts at boundaries that are not pleasing.
Removing blocking artifacts from traditional block-based transforms such as the DCT is difficult for many reasons. The boundary affects every coefficient. Each transform coefficient affects many spatial domain locations. Smoothness in the transform domain involves complex relationships between many coefficients. For example, the class of all 2D linear ramps in the spatial domain does not have a nice DCT representation. It is difficult to combine transform domain smoothness constraints and quantization constraints. Typically, iterative solutions are used, with an enhancement operation (smoothing/de-ringing/edge enhancement) being performed in the spatial domain followed by limiting in the transform domain to keep the enhancement within the quantization error.
Edges are often the cause of artifacts in an image. Edge extraction is well known in the art as a means to identify edges and to remove the edges from an image. The use of gaussians in edge detection has a long history. For instance, see E. Marr and E. Hildreth, xe2x80x9cTheory of Edged Section,xe2x80x9d Proc. R. SOC. London, Vol. 207, pp. 187-217, 1980; V. T. and Thomaso A. Poggio, xe2x80x9cOn Edge Detection,xe2x80x9d IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 8, pp. 147-63, 1986; L. Basano, D. Caprile, et al., xe2x80x9cEdge-Detection Schemes Highly Suitable for Hardware Implementation,xe2x80x9d J. Opt. Soc. Am., Vol. 5, pp. 1170-1175, 1988; and S. Mallate and S. Zhong, xe2x80x9cCharacterization of Signals from Multiscale Edges,xe2x80x9d IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 14, pp. 710-732, 1992. However, even though these methods for detecting edges existed in the prior art, there is always a desire to improve the edge detection so that reconstructions can be made with sharp edges without artifacts near the edges.
Compression is often very time consuming and memory intensive. It is desirable to perform compression faster and/or with reduced memory when possible. Some applications have never used compression because either the quality could not be assured, the compression rate was not high enough, or the data rate was not controllable. However, the use of compression is desirable to reduce the amount of information to be transferred and/or stored.
A method and apparatus for performing reconstruction is described. The method in the present invention provides for receiving DS and DD coefficients affected by a boundary, reconstructing SD coefficients to be smooth across the boundary, applying a vertical inverse transform individually on each tile, reconstructing D coefficients to be smooth across the boundary, and applying a horizontal inverse transform individually on each tile.